Restore IP addresses

Time: O(1); Space: O(1); medium

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example 1:

Input: s = “25525511135”

Output: [“255.255.11.135”, “255.255.111.35”]

Example 2:

Input: s = “1116512311”

Output: [“11.165.123.11”, “111.65.123.11”]

[3]:

class Solution1(object):
    """
    Time: O(N^M)=O(3^4)
    Space: O(N*M)=O(3*4)
    """
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        result = []
        self.restoreIpAddressesRecur(result, s, 0, '', 0)
        return result

    def restoreIpAddressesRecur(self, result, s, start, current, dots):
        # pruning to improve performance
        if (4 - dots) * 3 < len(s) - start or (4 - dots) > len(s) - start:
            return

        if start == len(s) and dots == 4:
            result.append(current[:-1])
        else:
            for i in range(start, start + 3):
                if len(s) > i and self.isValid(s[start:i + 1]):
                    current += s[start:i + 1] + '.'
                    self.restoreIpAddressesRecur(result, s, i + 1, current, dots + 1)
                    current = current[:-(i - start + 2)]

    def isValid(self, s):
        if len(s) == 0 or (s[0] == '0' and s != "0"):
            return False
        return int(s) < 256

[4]:

sol = Solution1()
s = "25525511135"
assert sol.restoreIpAddresses(s) == ["255.255.11.135", "255.255.111.35"]
s = "1116512311"
assert sol.restoreIpAddresses(s) == ["11.165.123.11", "111.65.123.11"]